Dynamic Group Link Prediction in Continuous-Time Interaction Network

1 Introduction

Link prediction, aiming to predict relationships between pairs of entities, has received wide attention as the increasing importance of network data [L¨u and Zhou, 2011; Mart´ınez et al., 2016; Kumar et al., 2020]. Since it helps us understand the inherent characteristics and evolutionary mechanisms of real-world networks, link prediction has been widely applied in many practical applications, such as knowledge graph completion [Rossi et al., 2021], biochemical reaction reconstruction [Nasiri et al., 2021] and content recommendation [Liu, 2022]. Almost all existing link prediction methods focus only on relationships between pairs of entities [Zhou, 2021], but the analysis of relationships between individuals and groups (i.e., group link prediction) also deserves attention since the patterns of relationship formation are not exclusively limited to a pair of entities [Stanhope et al., 2019; Sha et al., 2021].

∗The Corresponding Author

Nevertheless, in many real scenarios, our focus is on the prediction of future relationships between individuals and groups, such as organizers of hobby clubs expecting to invite target participants to their future events. The task of predicting future relationships between individuals and groups is known as continuous-time group link prediction. The difference between continuous-time group link prediction and continuous-time link prediction is shown in Figure 1. Despite recent efforts, three deficiencies remain in addressing continuous-time group link prediction problem with finegrained temporal information. First, previous methods rarely discuss future links between individuals and groups, but tend to mine missing ones. The assumption that all members are connected to the group at the same time makes the finegrained raw temporal information missing. Second, individuals are assumed to be isolated from each other, which neglects the neighborhood information that laterally depicts dynamic link preferences. Third, equal treatment of all group members leads to ignoring the diversity of members' importance in groups.

In this paper, we propose CTGLP, a novel continuous-time group link prediction method, to infer future relationships between individuals and groups in continuous-time dynamic networks with fine-grained temporal information. We first present CTGNN, a new graph neural network (GNN) with a continuous-time neighbor sampling strategy, to learn the embeddings of individuals, where a novel aggregation function is designed to jointly capture neighborhood features and finegrained temporal information. Second, an importance-based group modeling function is provided to model the latent representation of a group based on the embeddings of existing members. Finally, CTGLP outputs conditional probability distributions by using the embeddings of groups and finds out the link targets.

The contributions of this paper are summarized as follows.

• We propose a novel continuous-time group link prediction method CTGLP, which learns the patterns of link formation between individuals and groups in continuous-time dynamic networks with fine-grained temporal information and predicts the future links between individuals and groups.
• We propose a new graph neural network CTGNN to learn the representations of individuals. A continuoustime neighbor sampling strategy is designed to control the computational consumption, and an aggregation function CTAgg is presented to bias the aggregation weights of the features of sampled neighbors.
• We propose an importance-based group modeling function that models the groups into the latent space by measuring the importance of each member to the group based on the time of link formation.
• Extensive experiments on various datasets with and without unseen nodes are conducted to validate CTGLP and the experimental results demonstrate that CTGLP outperforms the baselines by a significant margin, with average gains of 13.4% and 13.2%.

2 RelatedWork

Link prediction. Based on the network structural similarity, heuristic link prediction methods, such as Common Neighbors (CN) [Liben-Nowell and Kleinberg, 2007] and Adamic-Adar (AA) [Adamic and Adar, 2003], assume that edges are more likely to exist between nodes with higher similarity scores. However, they only exploit shallow topological features of networks and lack general applicability. Besides, embedding techniques have also shown great potential in link prediction. Some embedding algorithms, such as DeepWalk [Perozzi et al., 2014], node2vec [Grover and Leskovec, 2016], HTNE [Zuo et al., 2018], etc., calculate the possibility of generating links between nodes using the embeddings. Nevertheless, some studies [Mara et al., 2020; Ghasemian et al., 2020] have demonstrated that embedding models may be inferior to well-designed mechanistic methods. Recently, some well-designed methods have shown their superiority in link prediction. TDGNN [Qu et al., 2020] leverages temporal information in dynamic networks to achieve continuous-time link prediction. GNMFCA [Lv et al., 2022] predicts future links using global and local information of temporal networks. GC-LSTM [Chen et al., 2022] applies an embedded Long Short-Term Memory (LSTM) of Graph Convolutional Network to perform dynamic link prediction. Dyngraph2vec [Goyal et al., 2020] integrates longerterm temporal information to learn node embeddings and predict future links. LP-ROBIN [Barracchia et al., 2022] utilizes incremental embedding to capture temporal dynamics and predict new connections. Despite the great success of link prediction, existing link prediction methods cannot be directly applied to group link prediction focusing on the relationships between individuals and groups because they only concentrate on the relationships between node pairs.

Group link prediction. Due to the inevitable limitations of link prediction methods applied to group link prediction, recent attempts have been made to solve the group link prediction problem. An LSTM-based model [Stanhope et al., 2019] is elaborately designed to address this problem. Feeding the sum of random vectors of members in a series of groups into LSTM, this model learns the embedding vectors of members and trains a classifier to predict the target. Despite the input of a series of group vectors, it ignores the neighborhood information that potentially expresses link preferences and may introduce information noise. Subsequently, a CVAE-based model [Sha et al., 2021] is proposed to estimate the probability of link existence by tuning the model parameters in a supervised manner. However, the absence of historical interaction information between individuals and groups prevents the model from addressing the problem of continuous-time group link prediction well. To further leverage historical information, CVAEH [Sha et al., 2021] additionally introduces a vector that encodes the previous groups. Nevertheless, the rough encoding of historical group information is still not a good solution. Summarizing existing group link prediction methods, they do not consider the fine-grained historical group information and fail to generalize to unseen data. Therefore, how to infer the future relationships between individuals and groups more effectively remains an open question.

3 Preliminaries

3.1 Definitions and Problem

Definition 1 (Continuous-time interaction network). A continuous-time interaction network G = (V,ET , T) consists of node set V , edge set ET and time set T , where vi ∈ V denotes the node in the network. etij ∈ ET denotes the edge/interaction between node vi and node vj at time t ∈ T .

Definition 2 (Group). Individuals jointly participating in a certain event are denoted as a group, i.e., si = {vt1 i,1 , vt2 i,2 , . . . , vtk i,k } ⊆ V , where i denotes the index of a group. vtk i,k denotes the k-th member node of group si, where tk denotes the link time and k ≥ 2 indicates that the number of members in a group should not be less than two. si ⊆ V indicates that the members of group si are from node set V .

Problem 1 (Continuous-time group link prediction). Given a continuous-time interaction network G = (V,ET , T), there is a node set V = {v1, v2, . . . , vN} with N nodes and a group set S = {s1, s2, . . . , sM} with M groups. For a group si = {vt1 i,1 , vt2 i,2 , . . . , vtk i,k } ⊆ V , max(t1, t2, . . . , tk) ≤ t with k members observed at current time t, the purpose of continuous-time group link prediction is to predict the target vt′ i,k+1 ∈ V \si that is most likely to be linked to group si at the future time t′ (t′ > t) based on the k known members in group si. Formally, it is defined as:

where F is the continuous-time group link prediction function. {vt1 i,1 , vt2 i,2 , . . . , vtk i,k } denotes the k known members of group si observed at current time t.

3.2 Construction of Continuous-Time Interaction Network

The historical relationships between individuals and groups can be represented as a continuous-time dynamic network by decomposing the links between external individuals and groups into multiple links between the external individuals and group members. Figure 2 shows how to build a continuous-time interaction network. If individual v links to group s at time t, individual v directly connects to the existing members of group s and the timestamps of the edges are all t, as v is the initiator of the link action. For example, user v4 links to group s3 containing members v1 and v5 at time t7, so two directed edges with timestamps of t7 from v4 to v1 and v5 are generated. Specially, if individuals vi and vj are the earliest two members in the group and their appearance times are ti and tj (ti < tj), a bidirectional edge with a timestamp tj will be added between them, as the appearance of the first two members indicates the formal formation of a group, and we consider the earliest two members to be visible to each other. For example, a bidirectional edge with a timestamp t4 exists between v1 and v5. Note that multiple edges exist between two individuals when they link to multiple same groups. For example, there are two edges between v4 and v5.

4 Methodology

Figure 3 shows the architecture of CTGLP. It consists of three main components: 1) Individual Representation Learning, 2) Importance-based Group Modeling and 3) Prediction. The Individual Representation Learning component aims to learn the latent embeddings of individuals using our proposed CTGNN. The Importance-based Group Modeling component is to model the latent representations of groups. The Prediction component aims to predict the targets.

4.1 Individual Representation Learning

Given a continuous-time interaction network G = {V,ET , T} with the initial random embeddings of nodes X = {⃗x1, ⃗x2, . . . , ⃗xN}, ⃗xi ∈ RD , individual representation learning part obtains the final latent embeddings of members Z = {⃗z1,⃗z2, . . . ,⃗zN},⃗zi ∈ Rd using our proposed CTGNN, where D and d are dimensions.

Continuous-Time Neighbor Sampling

Whereas previous GNNs simply examine k-hop neighborhood or the sampling schemes are only applicable to static networks [Zhou et al., 2020], the sampling process in all convolutional layers of our CTGNN are continuous-time respected, i.e., the time of the sampled edge should be less than that of the sampled edge of the previous layer. It can be ensured that all sampled neighbors of the central node exist in the past with respect to the central node, thus ensuring that all sampled neighborhood information exists prior to the current time during aggregation. We first define the time-limited neighbor set ΓT (u) of node u at time T :

Notably, node v may appear multiple times in ΓT (u) as multiple edges may exist between the same pair of nodes.

Then, in one convolutional iteration, we sample a fixed number of neighbors from ΓT (u) for node u:

where rθ(·) is the random sampling operation. θ is the neighbor sampling size and θ may be different for each layer.

Performing multiple sampling, CTGNN obtains higherorder neighbors and reduces the number of neighbors involved in the computation. The l-order continuous-time sampled neighbor set of node u at time T can be obtained by performing neighbor sampling operations l times:

where Sampl represents the sampling operation in the l-th convolutional layer. Ti+1 < Ti for 1 ≤ i < l, and T1 = T .

Embedding Update

By iteratively aggregating neighborhood features, GNNs learn the embeddings of nodes. A simple but effective aggregation scheme is mean operator [Kipf and Welling, 2017; Hamilton et al., 2017], which assumes that all neighbors of a central node contribute equally to the update of its new representation. However, mean operator may not be the optimal aggregation scheme for representation learning in continuous-time group link prediction, since the impact of different neighbors on the central node may vary dramatically depending on the time of link formation. Inspired by a study in event-based social networks [Pham et al., 2015], we argue that the groups users recently linked to are typically more representative of their preferences than those they linked to earlier. The manifestation of this insight in aggregation is that a newly connected neighbor has a higher contribution to the embedding update of the central node.

We provide an aggregation coefficient α calculated by our aggregation function CTAgg to bias the contribution of each neighbor. Given the edge time tij between node ui and uj as well as the edge time tik between node ui and uk, if tij > tik, the aggregation coefficient αt ij of node uj should be greater than the aggregation coefficient αt ik of node uk. At the l-th layer of CTGNN, the embedding update of node u at time t can be denoted as follows:

where AGG(·) is a function that aggregates the information of sampled neighbors and COM(·) is a function that combines information about sampled neighborhoods and the preupdate information of the central node in the previous layer. σ is a nonlinear activation. ˆN l t (u) is the l-th hop sampled neighbor set of node u at time t. W and w are learnable shared parameter matrices. αtuv is the aggregation coefficient of neighbor v at time t , and it can be interpreted as the contribution of v to the embedding update of the central node u at time t. The calculation of αtuv is defined as:

where tuv is the time of the edge between nodes u and v.

After obtaining the embedding ⃗hu of node u output by the last convolution iteration, a Multiple-layer Perceptron (MLP) with activation functions is employed to attain the final representation ⃗zu of node u:

where j is the index of neural layers. U and u are learnable parameter matrices.

4.2 Importance-based GroupModeling

The practice of previous work [Stanhope et al., 2019] is to sum up the vectors of all group members as the vector of the group. While it is intuitively sound, it ignores the fact that the influence of different members on the group may differ greatly. To this end, we present an importance-based group modeling strategy to represent groups into the latent space.

We first define an importance factor β to measure the importance of each group member. The value of the importance factor depends on the time when members are linked to the group, i.e., more recent members have larger importance factor values as they are intuitively more in line with the group formation trend. Formally, the importance factor of member k on group si is defined as:

where K is the number of members in group si and T is the prediction time for group si.

Given a group si with K members (i.e., si = {vi,1, vi,2, . . . , vi,K}) and the embeddings of these K members (i.e., {⃗zi,1,⃗zi,2, . . . ,⃗zi,K}), the importance-based group modeling part models the vectors of members as the vector ⃗mi ∈ Rs of group si, where s is the size of the group vector. The importance-based group modeling for group si is:

where C1, C2 and c are learnable parameter matrices.

4.3 Prediction

The final outputs of the importance-based group modeling part are fed into an MLP, and a Softmax activation function is employed to generate the link probability distributions between candidate individuals and groups. Formally, given the

Algorithm 1 Training of CTGLP

Input: Continuous-time interaction network G = (V,ET , T); set of node initial embeddings {⃗xv, ∀v ∈ V }; set of groups S = (s1, s2, . . . , sM), si ⊂ V .

Parameter: Convolutional layer depth K; neighbor sampling size θk, ∀k ∈ {1, . . . ,K}; learnable parameters.

Output: Continuous-time group link prediction function F. 1: while model not converge do

2: for i = 1 : M do 3: for u ∈ si do 4: ˆN K T (u) ←Sample-Neighbors(u,G,K, T , θ) 5: ⃗zu ← Update-Embedding(⃗xu, ⃗x ˆN K T (u) ,K) 6: end for 7: ⃗mi ← Group-Modeling({βu · ⃗zu, u ∈ si}) 8: Calculate link probabilities: Pi ← Softmax( ⃗mi, G, g, Q, q) 9: Obtain the target: ui ← argmax(Pi) 10: end for 11: Update parameters by stochastic gradient descent 12: end while

• 13: return F

latent vector ⃗mi of group si, the prediction process is:

where G, Q, g and q are learnable parameter matrices. k is the index of hidden layers. Pi is a link probability distribution whose elements represent the connection possibility between individuals and group si. The index corresponding to the element with the largest value in Pi is the index of the target predicted by CTGLP.

4.4 Training

Algorithm 1 shows the overall process of training. Let yi denote the one-hot encoding of the target in the i-th training sample and Pi be the link probability distribution output by CTGLP. Our objective function is formulated as:

where M denotes the number of group samples. N denotes the number of nodes in the node set V . yij and Pij are the j-th element of yi and Pi, respectively.

5 Experiments

5.1 Experimental Setup

Datasets. MovieLens-100K (ML100K for short) [Harper and Konstan, 2015] and MovieLens-25M (ML25M for short) [Harper and Konstan, 2015] contains rating data from users on movies. CiaoDVD [Guo et al., 2014] consists of DVD rating data. We select the rating data and regard the set of users who rate the same item as a group and take out the last member of each group as our prediction target. The number of members in a group are set to be 3 to 20. To construct the datasets without unseen nodes, we remove nodes that appear in validation and testing but not in training, and further clean the data. The statistics of datasets are shown in Table 1.

Table 1: Statistics of two versions of the three datasets. Note that the subscript w/o denotes the dataset without unseen nodes.

Metrics. To evaluate the performance of methods, we introduce three widely used evaluation metrics: Hit Ratio@K, Normalized Discounted Cumulative Gain@K and Mean Reciprocal Rank@K (denoted as HR@K, NDCG@K and MRR@K respectively). HR@K measures the ability to find the target and emphasizes the accuracy of prediction. NDCG@K and MRR@K measure the ability to rank targets and emphasize the ranking of targets.

Baselines. We compare our CTGLP with the following baselines: (1) Three Group link prediction methods. LSTMbased model (LSTM for short) [Stanhope et al., 2019] employs LSTM to combine the historical information of groups and outputs link probabilities. CVAE-based model (CVAE for short) [Sha et al., 2021] uses CVAE to reconstruct the membership of groups using a vector encoding an entire group and a vector encoding known members. CVAEH [Sha et al., 2021] additionally introduces a vector encoding historical information of previous groups for prediction. (2) Two neural network-based methods. MLP [Taud and Mas, 2018] utilizes mini-batch gradient descent strategy to update model parameters. GraphSAGE (GSAGE for short) [Hamilton et al., 2017] uses multi-layer aggregation functions to learn representations of nodes and obtains group vectors to make prediction. (3) Two heuristic link prediction methods. AA [Adamic and Adar, 2003] utilizes correlation coefficients of overlapping neighborhoods between nodes to measure the similarity between nodes. CN [Liben-Nowell and Kleinberg, 2007] uses the number of common neighbors between nodes to measure the similarity between nodes. Nodes with higher similarity to members of a group are considered more likely to link to the group. (4) Three network embedding methods. DeepWalk (DW for short) [Perozzi et al., 2014] uses random walks to generate vectors of nodes. node2vec (n2v for short) [Grover and Leskovec, 2016] learns node representations using biased random walks. HTNE [Zuo et al., 2018] integrates the Hawkes process and attention mechanism to learn the time-related representations of nodes. The individual-group link scores are obtained by aggregating the similarities between individuals.

Implementation details. For each dataset, we split it into 8:1:1 for training, validation and testing. We implement our CTGLP with PyTorch 1.6.0 and adopt the SGD as the optimizer. We apply batch normalization and dropout strategy with p = 0.5 for ML100K and CiaoDVD and p = 0.1 for ML25M. The dimension D of initial embeddings, the dimension d of hidden states and the dimension s of group vectors are all tested in {16, 32, 64, 128, 256, 512}. The batch size and learning rate are searched in {32, 64, 128, 256} and {0.005, 0.01, 0.05, 0.1} respectively. Two convolutional layers are employed in CTGNN, and the neighbor sampling sizes are empirically set to 25 and 10 respectively. For the parameters of our method, we initialize it randomly using a uniform distribution with values from 0 to 1. For baselines, we initialize the parameters according to the corresponding paper.

5.2 Performance Comparison

Performance on datasets with unseen nodes. From the overall results in Table 2, we observe that CTGLP outperforms most of the competing methods by a comfortable margin. On ML100K, our method obtains better performance than all baselines, especially in ranking targets. Specifically, CTGLP achieves average gains of 7.3%, 31.9% and 43.9% in terms of HR, NDCG and MRR scores. On CiaoDVD, CTGLP outperforms other baselines except for CVAE when K = 10. On ML25M, our method shows its great superiority in finding and ranking targets. In terms of three evaluation metrics, CTGLP obtains average gains of 11.45%, 14.7% and 11.1%, respectively.

Performance on datasets without unseen nodes. From the overall results in Table 3, we can see that CTGLP always achieves the best performance or the second-best one. On ML100Kw/o, our method is slightly worse than CVAE in HR scores, but it brings average gains of 22.4% and 45.9% in NDCG and MRR scores, which indicates that CTGLP can rank targets better. It is worth noting that most methods, including CTGLP, perform worse on this dataset than on ML100K. We argue that the removal of group members may affect the intrinsic nature of small dataset to a greater extent. On CiaoDVDw/o, our method always outperforms all competing models. Specifically, in three different metrics, CTGLP outperforms the best comparative method by 10.1%, 26.6% and 36.8% on average. On ML25Mw/o, CTGLP is inferior to heuristic link prediction methods AA and CN in the ability to rank targets, but it is still satisfactory in finding targets (obtains average gain of 13.9%). Besides, taskindependent embedding-based methods perform quite poorly, indicating that they are not suitable for continuous-time group link prediction. Compared to the performance on ML25M, the gains obtained by the three well-designed group link prediction methods (LSTM, CVAE and CVAEH) are much smaller than those of our method, suggesting that the lack of fine-grained temporal information and neighborhood features does limit the performance improvement of models.

Summaries. From the above analysis, several conclusions are drawn: (1) Our proposed CTGLP outperforms most baselines in datasets with and without unseen nodes, especially in finding targets. (2) Neighborhood information (the features of neighbors) is helpful to enhance the model performance. (3) Task-independent embedding-based methods are not suitable for group link prediction directly.

5.3 Comparison of Training and Inference Time

As shown in Figure 4, we can see that the training of our method is faster than LSTM and GSAGE and the inference is faster than CVAEH and GSAGE. MLP is always the fastest due to its simple architecture, while LSTM takes the longest time to train.

5.4 Ablation Study

The ablation study results of various components on the performance of our method are shown in Figure 5. From the overall results, we observe that: (1) Pure CTGLP performs much better than its three variants in terms of all metrics. (2) The performance of CTGLP w/o CTAgg is similar to that of CTGLP w/o IGM. (3) CTGLP w/o CTAgg&IGM obtains the worst performance and is far inferior to the other variants, especially in seeking out targets. The results verify our idea that, depending on the time, different neighbors contribute differently to the feature updates of the central nodes and different members have varying importance within the group.

5.5 Hyper-parameter Study

Effect of Embedding Dimension. The experimental results of the effect of embedding dimension are shown in Figure 6. Overall, the performance of our proposed CTGLP in three metrics increases with the increasing embedding size, but the performance deteriorates after reaching a dimension bottleneck. In particular, CTGLP makes the best performance when the hidden state size d is 128 and the group vector size s is 16. The changes in embedding sizes have only a slight effect on performance, which shows the robustness of our method. Intuitively, using a larger embedding size enhances the vector representation, but it is not always optimal and increases model complexity. Therefore, we need to choose an appropriate size to trade off performance and complexity.

Effect of Neighbor Sampling Size. The experimental results of the effect of neighbor sampling size are shown in Figure 7. In general, the performance of our method first improves and then decreases as the growing of neighbor sampling size. CTGLP achieves the best performance when size θ is 30 on the small dataset ML100K, and it performs best on CiaoDVD when size θ is 20. To sum up, a small size may make the neighborhood information insufficient to capture link preference and an overly large size may introduce information noise since not all neighbors are positive. The larger the sampling size, the greater the memory usage and time consumption. To keep the balance between performance and complexity, we need to use a proper sampling size.

6 Conclusion

In this paper, to address the dynamic group link prediction problem which concentrates on the future relationships between individuals and groups in continuous-time dynamic settings, we propose a novel continuous-time group link prediction method CTGLP. We first build continuous-time interaction networks based on the historical interactions between individuals and groups and present a new graph neural network CTGNN to learn the node embeddings, where a novel aggregation function is designed to jointly capture network structural features and temporal information. Then, we provide an importance-based group modeling function to model latent representations of groups, which can differentiate the contribution of members to group formation. Finally, the targets can be predicted using CTGLP based on group vectors. We compare CTGLP with ten baselines on various datasets and the experimental results show that CTGLP outperforms the state-of-the-art method. We also conduct a series of comprehensive experiments to analyze the effects of model components and hyperparameters on performance.

Acknowledgments

The work was supported by STI 2030' Major Projects (2021ZD0201300) and the Concept Grant of Hangzhou Institute of Technology of Xidian University (No.GNYZ2023XJ0409-2).